package sort;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

//基于比较的、原地的、内存的、升序的 排序
public class Sort {
    /**
     * 插入排序
     *
     * 时间复杂度：
     * 最好情况：O(n)    数组已经有序
     * 最坏情况：O(n ^ 2)    数组是逆序
     * 平均情况：O(n ^ 2)
     *
     * 对于插入排序，数组越趋于有序，耗时就越少
     *
     * 空间复杂度：
     * 最好 / 最坏 / 平均 ：O(1)
     *
     * 稳定性：稳定
     *
     * 同等规模下，耗时最少
     * @param array
     */
    //插入排序非递归
    public static void insertSort(int[] array){
        //有序数组：[0 , i]  无序数组：[i + 1,array.length]
        for(int i = 0;i < array.length - 1;i++){
            int x = array[i + 1];
            int j;
            for(j = i;j >= 0 && array[j] > x;j--){
                array[j + 1] = array[j];
            }
            array[j + 1] = x;
        }
    }
    //整理插入排序
    public static void insert2(int[] array){
        for(int i = 0;i < array.length;i++){
            int x = array[i];
            int j;
            for(j = i - 1;j >= 0 && array[j] > x;j--){
                array[j + 1] =array[j];
            }
            array[j + 1] = x;
        }
    }

    //插入排序递归
    public static void insertSortRecursion(int[] array,int from,int to){
        int size = to - from;   //有序区间的长度
        //无序区间的长度
        if(array.length - size < 1){
            return;
        }
        //[from,to)
        //要插入的元素一定在[to]
        int x = array[to];
        int i;
        for(i = to - 1;i >= 0 && array[i] > x;i--){
            array[i + 1] = array[i];
        }
        array[i + 1] = x;
        //[from,to + 1) 有序了
        insertSortRecursion(array,from,to + 1);
    }

    /**
     * 冒泡排序
     *
     * 时间复杂度：
     * 最好情况：O(n)    数组有序时
     * 最坏情况：O(n ^ 2)    数组逆序时
     * 平均情况：O(n ^ 2)
     *
     * 空间复杂度：
     * 最好 / 最坏 / 平均 ：O(1)
     *
     * 稳定性：稳定
     *
     * 同等情况下，耗时最多
     * @param array
     */
    public static void swap (int[] array,int i,int j){
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    //冒泡排序非递归
    public static void bubbleSort(int[] array){
        //需要进行 n - 1 次循环
        //无序区间：[0,array.length - i - 1)     有序区间：[array.length - i - 1,array.length)
        for(int i = 0;i < array.length - 1;i++){
            boolean sorted = true;
            for(int j = 0;j < array.length - i - 1;j++){
                if(array[j] > array[j + 1]){
                    swap(array,j,j + 1);
                    sorted = false;
                }
            }
            if(sorted){
                return;
            }
        }
    }

    //冒泡排序递归
    public static void bubbleSortRecursion(int[] array,int from,int to){
        int size = to - from;
        if(size <= 1){
            return;
        }
        for(int i = from;i < to - 1;i++){
            if(array[i] > array[i + 1]){
                swap(array,i,i + 1);
            }
        }
        //[from,to)
        //[from,to - 1) 无序
        //[to - 1,to) 有序
        bubbleSortRecursion(array,from,to - 1);
    }

    /**
     * 选择排序
     *
     * 时间复杂度：
     * 最好 / 最坏 / 平均：O(n ^ 2)
     *
     * 空间复杂度：
     * 最好 / 最坏 / 平均：O(1)
     *
     * 稳定性：不稳定
     * @param array
     */
    //一个有区间限制的选择排序
    public static void selectSort1(int[] array,int from,int to){
        for(int i = from;i < to - 1;i++){
            int maxIdx = from;
            for(int j = from;j < to - i;j++){
                if(array[j] > array[maxIdx]){
                    maxIdx = j;
                }
            }
            swap(array,maxIdx,to - i - 1);
        }
    }
    //选择排序非递归
    public static void selectSort(int[] array){
        //无序区间：[0，array.length - i)     有序区间：[array.length - i,array.length)
        //需要进行 n - 1 次选择
        for(int i = 0;i < array.length - 1;i++){
            int maxIdx = 0;
            for(int j = 0;j < array.length - i;j++){
                if(array[j] > array[maxIdx]){
                    maxIdx = j;
                }
            }
            swap(array,maxIdx,array.length - i - 1);
        }
    }
    public static void selectSort2(int[] array){
        //有序区间：[0,i)    无序区间：[i,array.length)
        for(int i = 0;i < array.length - 1;i++){
            int minIdx = i;
            for(int j = i + 1;j < array.length;j++){
                if(array[j] < array[minIdx]){
                    minIdx = j;
                }
            }
            swap(array,minIdx,i);
        }
    }

    //选择排序递归
    //无序区间：[from,to)
    public static void selectSortRecursion(int[] array,int from,int to){
        int size = to - from;
        if(size <= 1){
            return;
        }
        int maxIdx = from;
        for(int i = from + 1;i < to;i++){
            if(array[maxIdx] < array[i]){
                maxIdx = i;
            }
        }
        swap(array,maxIdx,to - 1);
        selectSortRecursion(array,from,to - 1);
    }

    /**
     * 希尔排序 (是插入排序的升级)
     *
     * 时间复杂度：O(n ^ 1.25)
     *
     * 空间复杂度：O(1)
     *
     * 稳定性：不稳定
     * @param array
     */
    public static void shellSort(int[] array){
        if(array.length == 0){
            return;
        }
        int gap = array.length / 2;
        while(true){
            //带间隔的分组插排
            for(int i = gap;i < array.length;i++){
                int x = array[i];
                int j;
                for(j = i - gap;j >= 0 && array[j] > x;j = j - gap){
                    array[j + gap] = array[j];
                }
                array[j + gap] = x;
            }
            if(gap == 1){
                break;
            }
            gap = gap / 2;
        }
    }

    /**
     * 堆排序 (是选择排序的升级)
     *
     * 时间复杂度：
     * 最好 / 最坏 / 平均 ：O(n * log(n))
     *
     * 空间复杂度：O(1)
     *
     * 稳定性：不稳定
     * @param array
     */

    public static void heapSort(int[] array){
        //从小到大排序 -> 建大堆
        createBigHeap(array,array.length);
        //循环选择的过程：一共需要 n - 1 次
        for(int i = 0;i < array.length - 1;i++){
            swap(array,0, array.length - i - 1);
            adjustDownBigHeap(array,array.length - i - 1,0);
        }
    }

    public static void adjustDownBigHeap(int[] array,int size,int index){
        while(2 * index + 1 < size){
            int maxIdx = 2 * index + 1;
            if(maxIdx + 1 < size && array[maxIdx + 1] > array[maxIdx]){
                maxIdx++;
            }
            if(array[index] >= array[maxIdx]){
                return;
            }
            swap(array,index,maxIdx);
            index = maxIdx;
        }
    }

    public static void createBigHeap(int[] array,int size){
        for(int i = (size - 2) / 2;i >= 0;i--){
            adjustDownBigHeap(array,size,i);
        }
    }

    /**
     * 快速排序
     *
     * 时间复杂度：
     * 最好情况：O(n * log(n))
     * 最坏情况：O(n ^ 2)
     * 平均情况：O(n * log(n))
     *
     * 空间复杂度：
     * 最好情况：O(log(n))
     * 最坏情况：O(log(n))
     * 平均情况：O(n)
     *
     * 稳定性：不稳定
     * @param array
     */

    //快速排序递归
    public static void quickSort(int[] array){
        quickSortInternal(array,0,array.length - 1);    //左闭右闭区间
    }

    //左闭右闭
    public static void quickSortInternal(int[] array,int from,int to){
        //本次待排序区间的元素个数  to - from + 1
        if(to - from + 1 <= 1){
            return;
        }
        //选区间的最右边的元素作为 pivot
        //最右边的元素下标为[to]

        //进行 partition 的操作
        //返回值是最终 pivot 的所在下标
        int i = partition3(array,from,to);

        //返回 i 下标，将[from,to]分为两部分
        //左边的 [from,i - 1] 的元素都是 <= pivot
        //右边的 [i + 1,to] 都是 >= pivot
        quickSortInternal(array,from,i - 1);
        quickSortInternal(array,i + 1,to);
    }

    //普通方法
    public static int partitionHoare(int[] array,int from,int to){
        int pivot = array[to];
        int left = from;
        int right = to;

        //当 [left,right] 区间内还有元素时，进行循环
        while(left < right){
            while(left < right && array[left] <= pivot){
                left++;
            }
            swap(array,left,right);
            while(left < right && array[right] >= pivot){
                right--;
            }
            swap(array,left,right);
        }
        return right;
    }
    //挖洞法
    public static int partitionDigHole(int[] array,int from,int to){
        int pivot = array[to];
        int left = from;
        int right = to;
        while(left < right){
            while(left < right && array[left] <= pivot){
                left++;
            }
            array[right] = array[left];

            while(left < right && array[right] >= pivot){
                right--;
            }
            array[left] = array[right];
        }
        array[left] = pivot;
        return left;
    }

    //前后指针法
    public static int partition3(int[] array,int from,int to){
        //b,d都指向from
        int pivot = array[to];
        //最开始
        //[from,b) -> [from,from) 区间内一个元素都没有
        //[b,d) -> [from,from) 区间内一个元素都没有
        //[d,to) ->[from,to) 整个区间所有元素都在里面
        int b = from;
        for(int d = from;d < to;d++){
            if(array[d] < pivot){
                swap(array,b,d);
                b++;
            }
        }
        swap(array,b,to);
        return b;
    }

    //进阶版
    public static void advancePartition(int[] array,int from,int to){
        //[from,b) 小于基准值
        //[b,d) 等于基准值
        //[d,g] 未比较的元素
        //(g,to] 大于基准值
        int pivot = array[to];

        int b = from;
        int d = from;
        int g = to;

        //[d,g] 这个区间内是没有进行比较的元素，当 d <= g 时说明还有元素
        while(d <= g){
            if(array[d] == pivot){
                d++;
            }else if(array[d] < pivot){
                swap(array,b,d);
                b++;
                d++;
            }else{
                swap(array,d,g);
                g--;
            }
        }
    }

    //快速排序的优化
    private static void quickSortInternal1(int[] array, int from, int to) {
        // 区间内的元素个数
        int size = to - from + 1;
        if (size <= 16) {
            insertSort(array, from, to);
        }

        // 三数取中法
        int leftValue = array[from];
        int rightValue = array[to];
        int midIdx = from + (to - from) / 2;
        int midValue = array[midIdx];

        if (leftValue <= rightValue) {
            if (rightValue <= midValue) {
                // rightValue 作为基准值
            } else if (leftValue <= midValue) {
                // midValue
                swap(array, midIdx, to);
            } else {
                // leftValue
                swap(array, from, to);
            }
        } else {
            // leftValue > rightValue
            if (leftValue <= midValue) {
                // leftValue
                swap(array, from, to);
            } else if (midValue <= rightValue) {
                // rightValue
            } else {
                // midValue
                swap(array, midIdx, to);
            }
        }

        int i = partition(array, from, to);

        quickSortInternal1(array, from, i - 1);
        quickSortInternal1(array, i + 1, to);
    }

    private static int partition(int[] array, int from, int to) {
        int pivot = array[to];
        int left = from;
        int right = to;

        while(left < right){
            while(left < right && array[left] <= pivot){
                left++;
            }
            swap(array,left,right);
            while(left < right && array[right] >= pivot){
                right--;
            }
            swap(array,right,left);
        }
        return left;
    }

    private static void insertSort(int[] array, int from, int to) {
        int size = to - from + 1;
        for (int i = 1; i < size; i++) {
            // 有序区间 [from, from + i)
            // 无序区间的第一个元素的下标 [from + i]
            int x = array[from + i];

            // 遍历有序区间
            int j;
            for (j = from + i - 1; j >= from && array[j] > x; j--) {
                array[j + 1] = array[j];
            }

            array[j + 1] = x;
        }
    }

    //快速排序非递归，用栈
    public static void quickSortNotRecursion(int[] array){
        Deque<Integer> stack = new LinkedList<>();
        //在栈中放入待排序区间的 from、to 的下标
        stack.push(0);
        stack.push(array.length - 1);
        while(!stack.isEmpty()){
            int to = stack.pop();
            int from = stack.pop();

            if(to - from + 1 <= 1){
                continue;
            }
            int i = partition(array,from,to);

            stack.push(from);
            stack.push(i - 1);

            stack.push(i + 1);
            stack.push(to);
        }
    }

    /**
     * 归并排序
     *
     * 时间复杂度：
     * 最好 / 最坏 / 平均：O(n * log(n))
     *
     * 空间复杂度：
     * 最好 / 最坏 / 平均：O(n)
     *
     * 稳定性：稳定
     * @param array
     */

    //归并排序非递归
    public static void mergeSort(int[] array){
        mergeSortInternal(array,0,array.length);
    }
    public static void mergeSortInternal(int[] array,int from,int to){
        if(to - from <= 1){
            return;
        }
        //把待排序区间对半分开
        //找到最中间位置的下标
        int mid = from + (to - from) / 2;
        //整个区间被切割成
        //[from,mid)
        //[mid,to)
        //按照相同的方式，处理剩下的左右区间
        mergeSortInternal(array,from,mid);
        mergeSortInternal(array,mid,to);

        //左右区间变得有序之后，将区间进行组合
        merge(array,from,mid,to);
    }
    public static void merge(int[] array,int from,int mid,int to){
        int size = to - from;
        //需要额外的空间，用来临时存放比较的数据
        int[] e = new int[size];
        int eIdx = 0;

        int leftIdx = from;     //左区间要处理的元素的下标
        int rightIdx = mid;      //右区间要处理的元素的下标

        //leftIdx == mid
        //rightIdx = to
        //这个时候两边的区间都没有元素了
        while(leftIdx < mid && rightIdx < to){
            if(array[leftIdx] < array[rightIdx]){
                e[eIdx] = array[leftIdx];
                eIdx++;
                leftIdx++;
            }else{
                e[eIdx] = array[rightIdx];
                eIdx++;
                rightIdx++;
            }
        }
        //如果有区间的元素被取完了，就将另外一个数组中的元素放到数组 e 最后
        while(leftIdx < mid){   //说明右区间元素取完
            e[eIdx] = array[leftIdx];
            eIdx++;
            leftIdx++;
        }
        while(rightIdx < to) {   //说明左区间元素取完
            e[eIdx] = array[rightIdx];
            eIdx++;
            rightIdx++;
        }
         //现在的元素都在数组 e 中，要将元素重新搬回到数组 array 中
        for(int i = 0;i < size;i++){
            array[from + i] = e[i];
        }
    }

    //因为在归并排序中需要有一个数组来进行临时存放数据，所以可以直接在方法的参数列表中传入一个数组
    public static void mergeSort2(int[] array){
        int[] e = new int[array.length];
        mergeSortInternal2(array,0,array.length,e);
    }
    public static void mergeSortInternal2(int[] array,int from,int to,int[] e){
        //除了方法的参数列表中多传入了一个数组，与上边的 mergerSortInternal 没有差别
        if(to - from <= 1){
            return;
        }
        int mid = from + (to - from) / 2;
        mergeSortInternal2(array,from,mid,e);
        mergeSortInternal2(array,mid,to,e);

        merge2(array,from,mid,to,e);
    }

    public static void merge2(int[] array,int from,int mid,int to,int[] e){
        int size = to - from;
        int eIdx = 0;
        int leftIdx = from;
        int rightIdx = mid;

        while(leftIdx < mid && rightIdx < to){
            if(array[leftIdx] <= array[rightIdx]){
                e[eIdx] = array[leftIdx];
                eIdx++;
                leftIdx++;
            }else{
                e[eIdx] = array[rightIdx];
                eIdx++;
                rightIdx++;
            }
        }
        while(leftIdx < mid){
            e[eIdx] = array[leftIdx];
            eIdx++;
            leftIdx++;
        }
        while(rightIdx < to){
            e[eIdx] = array[rightIdx];
            eIdx++;
            rightIdx++;
        }
        for(int i = 0;i < size;i++){
            array[from + i] = e[i];
        }
    }

    //归并排序，非递归
    public static void mergeSortNotRecursion(int[] array){
        int[] e = new int[array.length];
        for(int i = 1;i < array.length;i *= 2){
            for(int j = 0;j < array.length;j += (2 * i)){
                int from = j;
                int mid = from + i;
                if(mid >= array.length){
                    break;
                }
                int to = mid + i;
                if(to > array.length){
                    to = array.length;;
                }
                merge2(array,from,mid,to,e);
            }
        }
    }
    public static void main(String[] args) {
        System.out.println("冒泡排序：");
        int[] arr1 = {3,5,2,6,1,9,7,4,0,8};
        bubbleSort(arr1);
        System.out.println(Arrays.toString(arr1));

        int[] array1 = {3,5,2,6,1,9,7,4,0,8};
        bubbleSortRecursion(array1,0,array1.length);
        System.out.println(Arrays.toString(array1));

        System.out.println("插入排序：");
        int[] arr2 = {4,7,0,9,8,2,1,3,6,5};
        insertSort(arr2);
        System.out.println(Arrays.toString(arr2));

        int[] array2 = {4,7,0,9,8,2,1,3,6,5};
        insertSortRecursion(array2,0,1);
        System.out.println(Arrays.toString(array2));

        System.out.println("选择排序：");
        int[] arr3 = {8,5,7,1,4,2,3,6,0,9};
        selectSort(arr3);
        System.out.println(Arrays.toString(arr3));

        int[] array3 = {8,5,7,1,4,2,3,6,0,9};
        selectSortRecursion(array3,0,array3.length);
        System.out.println(Arrays.toString(array3));

        int[] array31 = {8,5,7,1,4,2,3,6,0,9};
        selectSort1(array31,1,5);
        System.out.println(Arrays.toString(array31));

        System.out.println("希尔排序：");
        int[] arr4 = {6,1,5,9,0,8,2,4,3,7};
        shellSort(arr4);
        System.out.println(Arrays.toString(arr4));

        System.out.println("堆排序：");
        int[] arr5 = {4,9,0,1,2,7,8,3,5,6};
        heapSort(arr5);
        System.out.println(Arrays.toString(arr5));

        System.out.println("快速排序：");
        int[] arr6 = {1,5,2,8,6,0,6,3,6,4,9,7,6};
        quickSort(arr6);
        System.out.println(Arrays.toString(arr6));

        int[] array6 = {1,5,2,8,6,0,3,4,7,9};
        quickSortNotRecursion(array6);
        System.out.println(Arrays.toString(array6));

        System.out.println("归并排序：");
        int[] arr7 = {1,8,0,3,2,5,4,6,7,9};
        mergeSort(arr7);
        System.out.println(Arrays.toString(arr7));

        int[] arr72 = {1,8,0,3,2,5,4,6,7,9};
        mergeSort2(arr72);
        System.out.println(Arrays.toString(arr72));

        int[] array7 = {1,8,0,3,2,5,4,6,7,9};
        mergeSortNotRecursion(array7);
        System.out.println(Arrays.toString(array7));
    }
}
